/*
Source : https://leetcode.com/problems/number-of-digit-one/
Author : nflush@outlook.com
Date   : 2016-07-19
*/

/*
233. Number of Digit One
 ?  

Question Editorial Solution  
 My Submissions 




?Total Accepted: 20756
?Total Submissions: 81206
?Difficulty: Hard



Given an integer n, count the total number of digit 1 appearing in all non-negative integers less than or equal to n.

For example:
 Given n = 13,
 Return 6, because digit 1 occurred in the following numbers: 1, 10, 11, 12, 13. 

Hint:
1.Beware of overflow.
*/
class Solution {
public:
    int countDigitOne(int n) {
        long int mask = 1;
        int sum = 0;
        for (; mask <= n; mask *= 10){
            sum += (n /(mask*10)) * mask;
            int x = n % (mask*10);
            if (x >= mask*2){ // 2~9
                sum += mask;
            } else if (x >= mask){ // 1
                sum += 1 + x % mask;
            }
        }
        return sum;
    }
};

